LRU Cache

In [137]:

    

class Node:
    def __init__(self, prev, next, key, value):
        self.prev = prev
        self.next = next
        self.key = key
        self.value = value


    

In [138]:

    

class Cache:
    def __init__(self, capacity):
        self.top = None
        self.last = None
        self.key_map = {}
        self.count = 0
        self.capacity = capacity
    
    def is_full(self):
        return self.count == self.capacity
    
    def insert(self, key, value):
        if self.is_full():
            cache._pop()
        node = Node(None, self.top, key, value)
        if self.top is None:
            self.top = node
            self.last = node
        else:
            self.top.prev = node
            self.top = node
        self.key_map[key] = node
        self.count += 1
        
    def get(self, key):
        node = self.key_map[key]
        self._delete_impl(node)
        self.insert(key, node.value)
        return node.value
    
    def set(self, key, value):
        node = self.key_map[key]
        self._delete_impl(node)
        self.insert(key, value)
        
    def delete(self, key):
        node = self.key_map[key]
        self._delete_impl(node)
        
    def _delete_impl(self, node):
        if node.prev is not None:
            node.prev.next = node.next
        else:
            self.top = node.next
                
        if node.next is not None:
            node.next.prev = node.prev
        else:
            self.last = node.prev
            
        del self.key_map[node.key]
        self.count -= 1
        
    def _pop(self):
        self._delete_impl(self.last)
        
    def __repr__(self):
        node = self.top
        values = []
        while node is not None:
            values.append(str(node.value))
            node = node.next
        return '[%s]' % ','.join(values)


    

In [154]:

    

cache = Cache(3)


    

In [155]:

    

cache.insert('test', 1)


    

In [156]:

    

print str(cache)


    

    




[1]

In [157]:

    

cache.insert('spoing', 2)


    

In [158]:

    

print str(cache)


    

    




[2,1]

In [159]:

    

print cache.get('test')


    

    




1

In [160]:

    

print str(cache)


    

    




[1,2]

In [161]:

    

cache.insert('boom', 3)
cache.set('test', 4)


    

In [162]:

    

cache.insert('yeah', 5)


    

In [163]:

    

print str(cache)


    

    




[5,4,3]

In [164]:

    

cache.delete('test')


    

In [165]:

    

print str(cache)


    

    




[5,3]

In [166]:

    

cache.delete('boom')


    

In [167]:

    

print str(cache)


    

    




[5]

In [152]:

    




    

In [ ]: